import java.util.Arrays;

public class Solution733 {

    int[] dx={1,0,-1,0};
    int[] dy={0,1,0,-1};

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int[][] visit=new int[image.length][image[0].length];
        dfs(sr,sc,image,visit,newColor,image[sr][sc]);
        return image;
    }

    private void dfs(int x, int y, int[][] image, int[][] visit, int newColor,int origin) {
        visit[x][y]=1;
        image[x][y]=newColor;
        for (int i=0;i<4;i++){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if (valid(xx,yy,image.length,image[0].length) && visit[xx][yy]==0 && image[xx][yy]==origin){
                dfs(xx,yy,image,visit,newColor,origin);
            }
        }
    }

    private boolean valid(int x, int y, int m, int n) {
        return x>=0 && y>=0 && x<m && y<n;
    }

    public static void main(String[] args) {
        int[][] image=new int[][]{{1,1,1},{1,1,0},{1,0,1}};
        image=new Solution733().floodFill(image,1,1,2);
        for (int[] ints : image) {
            System.out.println(Arrays.toString(ints));
        }
    }
}
